package JZ_Offer.dataStructure.tree;

import base.TreeNode;

import java.util.ArrayList;
import java.util.Deque;
import java.util.LinkedList;

/**
 * 按之字形顺序打印二叉树
 * <p>
 * 给定一个二叉树，返回该二叉树的之字形层序遍历，（第一层从左向右，下一层从右向左，一直这样交替）
 * <p>
 * 输入：
 * {8,6,10,5,7,9,11}
 * 返回值：
 * [[8],[10,6],[5,7,9,11]]
 */
public class JZ77_按之字形顺序打印二叉树 {

    private static ArrayList<ArrayList<Integer>> Print(TreeNode pRoot) {
        ArrayList<ArrayList<Integer>> objects = new ArrayList<>();
        if (pRoot == null) {
            return objects;
        }
        layer(objects, pRoot, 0, true);
        return objects;
    }

    private static void layer(ArrayList<ArrayList<Integer>> list, TreeNode node, int level, boolean left) {
        if (node == null) {
            return;
        }

        ArrayList<Integer> objects;
        if (level >= list.size()) {
            objects = new ArrayList<>();
            list.add(objects);
        } else {
            objects = list.get(level);
        }

        if (left) {
            objects.add(node.val);
        } else {
            objects.add(0, node.val);
        }

        layer(list, node.left, level + 1, !left);
        layer(list, node.right, level + 1, !left);
    }

    private static ArrayList<ArrayList<Integer>> Print1(TreeNode pRoot) {
        ArrayList<ArrayList<Integer>> lists = new ArrayList<>();
        if (pRoot == null) {
            return lists;
        }
        boolean left = true;
        Deque<TreeNode> deque = new LinkedList<>();
        deque.add(pRoot);
        while (!deque.isEmpty()) {
            int size = deque.size();
            ArrayList<Integer> sublist = new ArrayList<>();
            for (int i = 0; i < size; i++) {
                TreeNode node = deque.poll();
                if (node != null) {
                    if (left) {
                        sublist.add(node.val);
                    } else {
                        sublist.add(0, node.val);
                    }

                    deque.offer(node.left);
                    deque.offer(node.right);
                }
            }

            if (sublist.size() > 0) {
                lists.add(sublist);
            }
            left = !left;
        }

        return lists;
    }


    public static void main(String[] args) {
        TreeNode a = new TreeNode(1);
        TreeNode b = new TreeNode(2);
        TreeNode c = new TreeNode(3);
        TreeNode d = new TreeNode(4);
        TreeNode e = new TreeNode(5);
        TreeNode f = new TreeNode(6);
        TreeNode g = new TreeNode(7);

        a.left = b;
        a.right = c;
        b.left = d;
        b.right = e;
        c.left = f;
        c.right = g;

        ArrayList<ArrayList<Integer>> lists = Print1(a);

        System.out.println();
    }

}
